package org.nowcoder.leetcode.twoPointers;

/**
 * Title  : 167. Two Sum II - Input Array Is Sorted
 * Source : https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/?envType=study-plan-v2&envId=top-interview-150
 * Author : XrazYang
 * Date   : 2023-07-10
 */

public class LeetCode_167 {
    public int[] twoSum(int[] numbers, int target) {
        //暴力解法
        // int[] results = new int[2];
        // for (int i = 0; i < numbers.length; i++) {
        //     for (int j = i + 1; j < numbers.length; j++) {
        //         if (numbers[i] + numbers[j] == target) {
        //             results[0] = i + 1;
        //             results[1] = j + 1;
        //             return results;
        //         }
        //     }
        // }
        // return results;

        //优化一: 非递减顺序排列,可以利用二分查找
        // int[] results = new int[2];
        // for (int i = 0; i < numbers.length; i++) {
        //     int j = Arrays.binarySearch(numbers, i + 1, numbers.length,target - numbers[i]);
        //     if (j > 0) {
        //         results[0] = i + 1;
        //         results[1] = j + 1;
        //         return results;
        //     }
        // }
        // return results;

        //优化： 双指针
        int[] results = new int[2];
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                results[0] = left + 1;
                results[1] = right + 1;
                return results;
            }
        }
        return results;
    }
}
